# ot.py
# Resolves operations through operational transformation
#
# Copyright Notice:
#
# Copyright 2010 Nathanael Abbotts (nat.abbotts@gmail.com),
# 
#    Licensed under the Apache License, Version 2.0 (the "License");
#    you may not use this file except in compliance with the License.
#    You may obtain a copy of the License at
#
#        http://www.apache.org/licenses/LICENSE-2.0
#
#    Unless required by applicable law or agreed to in writing, software
#    distributed under the License is distributed on an "AS IS" BASIS,
#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#    See the License for the specific language governing permissions and
#    limitations under the License.
#
# About the Project:
#
#    This code is part of an ongoing project to fully emulate all the processes
#    of a Wave server. It is fully extensible, and can be used for a variety of
#    purposes, including testing, use as a client library, and many others.
#
#    The latest source code can be found at http://wave-emulator.googlecode.com,
#    along with links to or code for any official extensions, and a full wiki
#    explaining all code functions & best uses, and an issue tracker & feature 
#    request process.
from collections import deque


import error

RETAIN = 'RETAIN'
INSERT = 'INSERT'
DELETE = 'DELETE'

# Just a note to anyone modifying this - unless you've fully tested any code
# you put in the '- Transform against XYZ -' sections, as it is really
# important that no slip-ups happen with them, as it will be likely to go
# unnoticed.
#                                  --THANKS!--
#
# Note this will not apply once the testing code is written to check these :)
class Transform(object):
    """Transforms/Zips two operation queues

    Processes 2 operation queues, transforming them against each other, then
    outputing two queues of transformed operations.

    Note that all operations from the in queues should have already been
    executed where they originated from, but nowhere else. 

    Usage #1: When you have no out queues predefined.
    trans1, trans2 = ot.Transform(in_queue_1, in_queue_2).transform()

    Usage #2: When you have 2 out queues predefined.
    ot.Transform(in_queue_1, in_queue_2, out_queue_1, out_queue_2).transform()
    """
    def __init__(self, in_queue_1, in_queue_2,
                 out_queue_1 = None, out_queue_2 = None):
        """Sets up instance variables"""
        self.in_1 = in_queue_1
        self.in_2 = in_queue_2
        if (out_queue_1 != None) and (out_queue_2 != None):
            self.out_1 = out_queue_1
            self.out_2 = out_queue_2
        else:
            self.out_1 = Operation_Queue()
            self.out_2 = Operation_Queue()
    def transform(self, num = -1):
        if num < 0:
            # Transform all code.
            pass
        else:
            # Transform 'num' number of operations & no more.
            pass
        # TODO: Make sure op.copy() is used so that the original op remains
        # unchanged, so that it can be transformed against another op too.
    # ------------------- Transform against RETAIN ----------------------------
    def retain_retain(self, op1, op2):
        """Transforms a retain against (after) a retain

        As a retain operation doesn't actually modify text, operations after it
        do not require transformation."""
        if op1.position == op2.position:
            return op1, op2
        elif op1.position < op2.position:
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    def retain_insert(self, op1, op2):
        """Transforms an insert against (after) a retain
        
        As a retain operation doesn't actually modify text, operations after it
        do not require transformation."""
        if op1.position == op2.position:
            return op1, op2
        elif op1.position < op2.position:
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    def retain_delete(self, op1, op2):
        """Transforms a delete against (after) a retain

        As a retain operation doesn't actually modify text, operations after it
        do not require transformation."""
        if op1.position == op2.position:
            return op1, op2
        elif op1.position < op2.position:
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    # ------------------- Transform against INSERT ----------------------------
    def insert_retain(self, op1, op2):
        """Transforms a retain against (after) an insert

        If positions are identical, retain does not need transformed.
        
        If the retain is at a position after the insert, it's position must be
        increased by len(op1.param).

        If the retain occurs before the insert, retain does not need transformed
        """
        # TODO: !
        if op1.position == op2.position:
            return op1, op2
        elif op1.position < op2.position:
            op2.param += len(op1.param)
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
        # TODO: FIX ^^^THIS^^^ as we need to work out the *new* position by
        # doing op2.position + op2.param
    def insert_insert(self, op1, op2):
        """Transforms an insert against (after) an insert

        If the positions are identical, ????

        If the 2nd insert occurs at a position after the first, it requires
        transformation by increasing it's position by len(op1.param).

        If the 2nd insert occurs at a position before the first, it does not
        require transformation."""
        if op1.position == op2.position:
            #TODO: What should be done here? Do we allow them to both add
            # text at the same point? What algorithm should be used?
            return op1, op2
        elif op1.position < op2.position:
            op2.position += len(op1.param)
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    def insert_delete(self, op1, op2):
        """Transforms a delete against (after) an insert
        
        If the positions are identical, increase the delete position by
        len(op1.param).

        If the delete occurs after the insert, increase the delete position by
        len(op1.param).

        If the delete occurs before the insert, it does not require a
        transformation.
        """
        if op1.position == op2.position:
            op2.position += len(op1.param)
            return op1, op2
        elif op1.position < op2.position:
            op2.position += len(op1.param)
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    # ------------------- Transform against DELETE ----------------------------
    def delete_retain(self, op1, op2):
        """Transforms a retain against (after) a delete"""
        # TODO: !
        if op1.position == op2.position:
            pass
        elif op1.position < op2.position:
            pass
        elif op1.position > op2.positon:
            pass
        # TODO: WRITE ^^^THIS^^^ as we need to work out the *new* position by
        # doing op2.position + op2.param
    def delete_insert(self, op1, op2):
        """Transforms an insert against (after) a delete

        If the insert occurs at the same position as the delete, no transform
        is required.

        If the insert occurs after the delete, it needs to be transformed by
        reducing it's position by op1.param.

        If the insert occurs before the delete, no transform is required."""
        if op1.position == op2.position:
            return op1, op2
        elif op1.position < op2.position:
            op2.position -= op1.param
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2
    def delete_delete(self, op1, op2):
        """Transforms a delete against (after) a delete
        
        If the operations occur at the same position:
            And they are the same length or the 2nd is shorter, discard the 2nd
            (reduce param to 0).
            If the 2nd is longer, reduce op2.param to the difference in length.

        If the 2nd operation occurs after the first, transform it according to
        the following:
            Reduce op2.position by the amount op1.param.
            Ajust for overlap (if op1 deletes some of what op2 was going to)
            correct this by reducing op2.param accordingly.
        
        If the 2nd operation occurs before the first, no transform in required.
        """
        if op1.position == op2.position:
            op2.param -= op1.param
            if op2.param < 0: op2.param = 0
            return op1, op2
        elif op1.position < op2.position:
            if op1.position + op1.param > op2.position:
                op2.param -= op1.position + op1.param - op2.position
            op2.position -= op1.param
            return op1, op2
        elif op1.position > op2.positon:
            return op1, op2

class Operation(object):
    """An individual operation"""
    def __init__(self, position, operation = RETAIN, param = 0):
        self.position = position
        self.operation = operation
        # param is either a number, in the case of RETAIN or DELETE, or a string
        # in the case of INSERT. The most likely error here (trying to delete a
        # string) has been tested for and fixed.
        if operation == DELETE and isinstance(param, str):
            self.param = len(param)
        else:
            self.param = param
        self.is_transformed = False
    def execute(self, blip):
        """Executes the operation on 'blip'"""
        pass
    def copy(self):
        """Returns a new Operation instance with identical values"""
        return Operation(self.position, self.operation, self.param)

class Operation_Queue(deque):
    """A queue of Operation objects

    When instantiating, you can provide any number of Operation instances as
    operations."""
    def __init__(self, *args, position = 0,):
        """Creates an Operation Queue."""
        super(Operation_Queue, self).__init__(args)
        self.position = position
    def append(self, position, operation, arg):
        super(Operation_Queue, self).append(Operation(position, operation, arg))
    def appendleft(self, position, operation, arg):
        super(Operation_Queue, self).appendleft(Operation(position, operation,
                                                          arg))
